/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-07
 * Time: 11:59
 */
public class BinarySearchTree {
    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;


    //插入一个新节点
    public boolean insert(int key) {
        if (this.root == null) {
            this.root = new TreeNode(key);
        }
        TreeNode cur = this.root;
        TreeNode prev = null;
        //通过与一个个结点的值进行比较，找到应该插入的位置
        while (cur != null) {
            if (key > cur.key) {
                prev = cur;
                cur = cur.right;
            }else if (key < cur.key){
                prev = cur;
                cur = cur.left;
            }else {
                return false;//说明搜索二叉树中已经存在该值
            }
        }
        //与插入位置的前一个节点的值进行比较，大于就放右树，否则放左树
        if (key > prev.key) {
            prev.right = new TreeNode(key);
        }else {
            prev.left = new TreeNode(key);
        }
        return true;
    }
    //查找key是否存在
    public TreeNode search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (key > cur.key) {
                cur = cur.right;
            }else if (key < cur.key) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }
    //删除key的值
    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode prev = null;
        //将要删除的结点找出来
        while (cur != null) {
            if (key > cur.key) {
                prev = cur;
                cur = cur.right;
            }else if (key < cur.key) {
                prev = cur;
                cur = cur.left;
            }else {
                break;
            }
        }
        if (cur == null) {
            return false;
        }
        //分情况进行处理
        if (cur.left == null) {
            //当它无左树时
            if (cur == root) {
                root = cur.right;
            }else if (prev.right == cur) {
                prev.right = cur.right;
            }else {
                prev.left = cur.right;
            }

        }else if (cur.right == null) {
            //当它无右树时
            if (cur == root) {
                root = cur.left;
            }else if (prev.right == cur) {
                prev.right = cur.left;
            }else {
                prev.left = cur.left;
            }

        }else {
            //当它左树和右树都在时
            //采用替换删除的方法
            //找出右树的最小值
            TreeNode t = cur.right;
            TreeNode tp = cur;
            while (t.left != null) {
                tp = t;
                t = t.left;
            }
            cur.key = t.key;
            if (tp.left == t) {
                tp.left = t.right;
            }else {
                tp.right = t.right;
            }

        }
        return true;
    }

}
